#include "stdio.h"
#include "stdlib.h"

int num_arr[] = {13, 6, 8, 15, 9, 12, 7, 1};
int len = sizeof(num_arr) / sizeof(int);

// 合并两个有序数组
void merge(int arr[], int low, int mid, int high) {
    int i,k;
    int *tmp = (int *)malloc((high - low + 1)*sizeof(int));
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;

    for (k = 0; left_low <= left_high && right_low <= right_high; k ++) {
        if (arr[left_low] <= arr[right_low]) {
            tmp[k] = arr[left_low];
            left_low ++;    
        }
        else {
            tmp[k] = arr[right_low];
            right_low ++;
        }

    }

    if (left_low <= left_high) {
        for (i = left_low; i <= left_high; i++) {
            tmp[k] = arr[i];
            k ++;
        }
    }

    if (right_low <= right_high) {
        for (i = right_low; i <= right_high; i++) {
            tmp[k] = arr[i];
            k ++;
        }
    }

    for (i = 0; i < high - low + 1; i ++) {
        arr[low + i] = tmp[i];
    }
    free(tmp);
    return;
}

void merge_sort(int arr[], int left, int right) {
    int mid = 0;
    if (left < right) {
        mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
    return; 
}
int main()
{
    int i;
    merge_sort(num_arr, 0, len - 1);
    for (i = 0; i < len; i ++) {
        printf("%d ", num_arr[i]);
    }
    return 0;
}
